/**
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘……
 * 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 *
 * @author yongting zhang
 * @date 2020-12-03 09:18
 */
public class Hw2 {

    public static void main(String[] args) {
        //与0-1背包问题一样
        {
            int[] values = {600, 300, 500, 400, 600};
            int[] weights = {2, 2, 6, 5, 4};
            int max = 10;
            System.out.println("最大黄金：" + method(values, weights, max));
        }
        {
            int[] values = {600, 300, 500, 2000, 600};
            int[] weights = {2, 2, 6, 10, 4};
            int max = 10;
            System.out.println("最大黄金：" + method(values, weights, max));
        }
    }

    public static int method(int[] values, int[] weights, int max) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || max <= 0) return 0;

        //dp数组  dp[i-1]  i从1开始
        int[][] dp = new int[values.length + 1][max + 1];

        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {
                //选择的物品超过最大承重
                if (weights[i - 1] > j) {
                    //不能选该物品 等于上轮的最大价值
                    dp[i][j] = dp[i - 1][j];
                }
                //选择的物品不超过最大承重
                else {
                    //上轮的最大价值
                    int proValue = dp[i - 1][j];
                    //选择该商品后的最大价值
                    int curValue = values[i - 1] + dp[i - 1][j - weights[i - 1]];
                    //两者取最大值
                    dp[i][j] = Math.max(proValue, curValue);
                }

            }
        }

        int mv = dp[values.length][max];
        int j = max;
        String numStr = "";
        for (int i = values.length; i > 0; i--) {
            if (dp[i][j] != dp[i - 1][j]) {
                //取了当前的矿
                numStr = numStr + " " + i;
                j = j - weights[i - 1];
            }
            if (j == 0) {
                break;
            }
        }
        System.out.println("金矿为：" + numStr);
        return mv;

    }
}
